// 二叉树的最近公共祖先
package Leetcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class Solution236 {
    public Map<TreeNode, TreeNode> parent = new HashMap<>();
    public Set<Integer> path = new HashSet<>();

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        parentDFS(root);

        while (p != null) {
            path.add(p.val);
            p = parent.get(p);
        }

        while (q != null) {
            if (path.contains(q.val))
                return q;
            q = parent.get(q);
        }
        return null;
    }

    public void parentDFS(TreeNode node) {
        if (node.left != null) {
            parent.put(node.left, node);
            parentDFS(node.left);
        }
        if (node.right != null) {
            parent.put(node.right, node);
            parentDFS(node.right);
        }
    }
}
